Point labeling on maps is a traditional research topic. It's a classical problem to label points on maps in cartology and a key problem in geography information system. What is the so-called point labeling on maps? Try to put the corresponding names of cities on their right positions on a map of China, this process is called labeling. FIG. 1 shows a map of some region near Beijing() 10, all the points on said map are labeled. However, the labeling results of the map is not an optimized solution. For example, the “” 20, on the up left corner, as well as the “” 30 on the down right corner, should not be labeled since the points are not on the map and these two labels are meaningless; the label “” 40 lies near two points, and it is easy to lead to misunderstandings.
Generally speaking, labeling is used to help users understand the meaning of the corresponding point easily, thereby the label is generally very close to the point. And there are always many positions applicable. For example, there are four applicable positions called candidate label positions in FIG. 2 and FIG. 3 respectively. Obviously, there are many other candidate label positions too, such as the combination of candidate label positions in FIG. 2 and FIG. 3, or arbitrary slides and rotations of candidate label positions near the point, and so on.
After the candidate label set of points is determined, choices of different label positions should coincide with certain viewpoints of aesthetics. For example, in FIG. 2, the visual comfort index decreases in the sequence of position 1, 2, 3 and 4. Therefore, if possible, the position with high visual comfort index should be chosen, which means different candidate positions have different priorities when labeling points on maps. This is possible by referring to the cases showed in FIGS. 4 and 5: if P1, a candidate label position of point P have some other points (FIG. 4), or the position has been determined by other points as a label position (FIG. 5), labeling point P on the position of P1 definitely leads to misunderstanding when displaying. Therefore, when evaluating a method for determining point label position on maps, the criterion should include labeling as many points as possible without overlap and meeting the requirements of aesthetics as well.
When browsing a map on computer, the point label is usually needed for helping understanding contents of the map. For example, there are coordinates (e.g. longitudes and latitudes) and contents of map points (that is, their labels) stored in geographical information systems. When displaying the map in a computer, the position and the rectangle size (that the widths and the lengths of the rectangles in FIG. 2 to FIG. 5) of the point label can be determined according to contents of map points, the display scale and the size of monitor users defined in advance. After the label positions of each point according to rules of point labeling, the points and the contents thereof on the map can be well displayed on the computer screen.
FIG. 6 shows a simplified model of WebGIS map browsing service of the present invention. In FIG. 6, browser A sends a request to WebGIS server B for browsing a map. After receiving the request, the WebGIS server B sends pertinent map data back to browser A.
When browsing the map through the network, taking the web geographical information system (WebGIS) as an example, the server in WebGIS is usually a computer with large storage capacity and excellent computing ability. Therefore, the geographical information is always stored in the server. Clients can be simple computers, mobile telephones, or PDAs and so on. The working pattern is as follows. A client requests for service from a server first, for example, displaying all the book stores near Tsinghua University with display scale S on the monitor whose width is W, and height, H. Then the server responses to request of the client by sending back the point positions, the point label positions and label contents after determining the position of points and points' labels according to the data supplied by the client on the client screen. Thereby all the bookstores near Tsinghua University will be displayed on the client side. This is a service application of single client. The server can deal with it in real time. The time needed for the server to determine the label position can be approximately ignored, and the time delay can be ignored on the client side as well. However, when a plurality of clients (such as 10,000 clients) apply for such services simultaneously, the time needed for determining the label position by the server cannot be ignored. This will lead to the case in which, the client cannot receive the response for a long time after applying for the service, and the quality of service will be decreased as well.
FIG. 7 shows a general working flow chart of WebGIS server. As shown in the drawings, it starts at Step S1, and waits for a users' request at Step S2. Then goes to Step S3 if there is a service request sent by a user. It reads in the display scale, point positions and size of label of the user, determining the label positions with traditional methods, and sends the determined result back to the user.
In traditional point labeling methods, the research target of map point labeling is the point set in a given area as well as the candidate label position set of each point. The candidate label position set of the unlabeled points can be classified into two categories:
1. Limited candidate label positions;
2. Unlimited sliding label positions.
No matter how large the number of the candidate label set is, the label determining method has been proved to be a NP problem. Example of point label methods that have been disclosed include: Expert System, Simulated Annealing method, Greedy method, Discrete Gradient method, Exhaustive Search method, Heuristic Method, etc. According to the research results of Jon Christonson et al., the way of point label with the best quality is the one of Simulated Annealing. Its label efficiency has priority to that of Exhaustive Search, Greedy, Discrete Gradient, and so on. However, the time consumption of Simulated Annealing is great.
When browsing maps on the web, under a certain label quality, users care more about the label efficiency, that is, the time complexity of the point label determine method. Especially in the pop Location-based Services (LBS) in WebGIS, it is possible for a large number of people to apply for the service of browsing the same map at the same time. This is a challenge to the capability of the map label determining method. And great effort is needed to smooth the system and the method for determining map point label on the web.
By far a better heuristic way for determining point label used on web is the one provided by Wagner (cf: Frank Wagner, Alexander Wolff, Vikas Kapoor and Tycho Strijk. Three rules suffice for good label placement. Algorithmica Special Issue on GIS, 2000. http://www.math-inf.uni-greifswald.de/map-labeling/bibliography, the following is called reference 1). While using the point label determining method to determine point label position on WebGIS map in real time, the time needed for determining can be largely reduced with little loss of labeling efficiency compared with Simulated Annealing methods.
LBS is generally used in urban areas where the population densities are always high and the activity areas of human being are relatively concentrated. It is obvious that, the displayed map areas which users care for are identical with the activity areas. When different users apply for the service of point label of local area, there are a larger number of area overlaps in multi-user service requests. If each user obtains label positions via real-time determining, the repeated determination will consume much time of the server; furthermore, when the number of points through real-time determining is large, the determining time needed for a single user cannot be ignored. A similar problem lies in other maps browsing services through networks, such as browsing the distribution of electronic components on circuit board stored in servers via networks, and so on.
The long time consumption in real-time computation indicates that a point label result of certain area can be pre-determined with certain display scale and stored in the server in advance. When users request for map displaying service (label), they only need to recall the results in the server, and this can save much time. However, when the display scale is changed, it will lead to label overlaps, the deduction of labeling efficiency, etc, though simple recall stories in the server.